/**
    ******************************************************************************
    * @file    bTree.c
    * @author  debian
    * @version V1.0.0
    * @date    2020-01-06
    * @brief   B树
    ******************************************************************************
    * @attention
    *
    *
    ******************************************************************************
    */ 

/* Includes ------------------------------------------------------------------*/
#include "bTree.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

/** @addtogroup DataStruct_Driver
    * @{
    */

/** @addtogroup bTree
    * @{
    */

/* Private typedef -----------------------------------------------------------*/

/* Private define ------------------------------------------------------------*/

/* Private macro -------------------------------------------------------------*/

/* Private variables ---------------------------------------------------------*/

/* Private function prototypes -----------------------------------------------*/

/* Private functions ---------------------------------------------------------*/


/** @defgroup bTree_Exported_Functions bTree Exported Functions
    * @{
    */

/** @defgroup bTree_Exported_Functions_Group1 Initialization and deinitialization functions
    *  @brief    Initialization and Configuration functions
    *
@verbatim    
    ===============================================================================
                ##### Initialization and deinitialization functions #####
    ===============================================================================
    [..]
        This section provides functions allowing to initialize and de-initialize the bTree
        to be ready for use.
 
@endverbatim
    * @{
    */ 

/**
    * @brief  创建bTree对象
    * @param  
    * @retval 
    */ 
   

/**
    * @brief  销毁bTree对象
    * @param  
    * @retval 
    */ 
    
    
/**
    * @}
    */

/** @defgroup bTree_Exported_Functions_Group2 operation functions 
    *  @brief   operation functions
    *
@verbatim   
    ===============================================================================
                        ##### operation functions #####
    ===============================================================================
    [..]
        This subsection provides a set of functions allowing to manage the bTree.

@endverbatim
    * @{
    */

	static void btree_printf(struct bTree_node *node);

/**
    * @brief  B树的搜索
    * @param   p 输出参数
    * @retval 
    */ 
    int bTree_search(struct bTree_node *node, Elemtype k, struct bTree_position *p)
	{
		int i = 0;
		assert(p);
	
		//循环判断k在结点上是哪个位置
		while(i < node->bst.num && k > node->bst.key[i]) {
			i++;
		}

		if(i < node->bst.num && k == node->bst.key[i]) {
			//返回结点的指针和结点的第几个元素
			p->x = node;
			p->i = i;
		} else if(node->bst.leaf)  {		//如果是叶子结点
			p->x = NULL;
			p->i = 0;
		} else {
			bTree_search(node->bst.child[i], k, p);
		}

		return 0;
	}


/**
    * @brief  B树创建结点
    * @param   p 输出参数
    * @retval 
    */ 
    struct bTree_node *bTree_creat_node(struct bTree *T, Elemtype k, int leaf)
	{
		//申请一个结点
		struct bTree_node *node = (struct bTree_node *)malloc(sizeof(struct bTree_node));
		assert(node);

		//填充数据
		node->data = 0;				//不知道data是怎么用，以后分析一些具体使用B树的实例应该就清楚了
		node->bst.num = 0;			//node结点个数
		node->bst.leaf = leaf;		//是否是叶子结点，1为叶子节点，0为非叶子节点
		node->bst.key = (Elemtype *)calloc(1, (2*T->degree-1)*sizeof(Elemtype));   //2t-1个关键字
		node->bst.child = (struct bTree_node **)calloc(1, (2*T->degree)*sizeof(struct bTree_node *));

		return node;
    }

/**
	* @brief  B树释放结点
	* @param   p 输出参数
	* @retval 
	*/ 
	int bTree_destroy_node(struct bTree_node *node)
	{
		assert(node);

		//释放关键字内存
		free(node->bst.key);

		//释放指向孩子结点指针内存
		free(node->bst.child);

		//释放结点
		free(node);

		return 0;
	}


/**
	* @brief  B树分裂结点
	* @param   要分裂的结点的父节点x,和指向要分裂结点的x的下标i
	* @retval 
	*/ 
	static int btree_split_child(struct bTree *T, struct bTree_node *x, int i)
    {
		int j = 0;
		//获取到要分裂的结点的指针
		struct bTree_node *y = x->bst.child[i];

		//创建一个新的结点
		struct bTree_node *z = bTree_creat_node(T, 0, y->bst.leaf);		

		//拷贝y的一半关键字给z
		for(j = 0; j<T->degree-1; j++)
		{
			z->bst.key[j] = y->bst.key[T->degree+j];   
		}

		//判断是否是是叶子结点，如果不是，拷贝指针
		if(!y->bst.leaf)
		{
			for(j = 0; j<=T->degree-1; j++)
			{
				z->bst.child[j] = y->bst.child[T->degree+j];   
			}
		}

		//更新y，z的num
		y->bst.num = T->degree-1;
		z->bst.num = T->degree-1;

		//移动x的结点，留下i的空位，然后插入
		for(j=x->bst.num; j>=i; j--)
		{
			x->bst.key[j+1] = x->bst.key[j];
		}

		x->bst.key[i] = y->bst.key[T->degree-1];

		//移动x的孩子结点，添加指针z的指针
		for(j=x->bst.num-1; j>=i; j--)
		{
			x->bst.child[j+1] = x->bst.child[j];
		}

		x->bst.child[i+1] = z;
		x->bst.num += 1;

		return 0;
	}


/**
	* @brief  B树插入结点
	* @param   输出参数
	* @retval 
	*/ 
	static int btree_insert_nonfull(struct bTree *T, struct bTree_node *node, Elemtype k) 
	{
		int i = node->bst.num - 1;
		//这个才是真正的插入函数

		if(node->bst.leaf)  {		
			//如果是叶子结点，就可以插入了

			//循环比较关键字，看插入哪个位置
			while(i>=0 && k<node->bst.key[i]) {
				node->bst.key[i+1] = node->bst.key[i];  	//能到这一步插入了，就都不是满结点，不需要考虑溢出问题
				i--;
			}

			//以i为分界，往后移动，留下i作为新结点的位置
			node->bst.key[i+1] = k;
			node->bst.num++;
		}else { 					//不是叶子结点
			//循环比较关键字，看插入哪个位置
			while(i>=0 && k<node->bst.key[i]) i--;
		
			//判断child[i]指向的子结点是否是满的
			if(node->bst.child[i+1]->bst.num == T->degree*2-1) {
				//分裂
				btree_split_child(T, node, i+1);
				//分裂完成之后，再判断一下新添加到x结点的i+1的值和k比较
				if(k > node->bst.key[i+1]) i++;
			}

			btree_insert_nonfull(T, node->bst.child[i+1], k);
		}

		return 0;
	}

/**
    * @brief  B树插入结点
    * @param   输出参数
    * @retval 
    */ 
    int bTree_insert(struct bTree *T, Elemtype k)
	{
		//插入结点的时候，要先判断是否是满结点，判断满结点也是分两种情况，一种是根结点，一种是其他结点
		
		//根结点为满结点的时候
		if(T->root->bst.num == T->degree*2-1) {
			//分裂根结点

			//创建结点x
			struct bTree_node *x = bTree_creat_node(T, 0, 0);	
			x->bst.child[0] = T->root;
			T->root = x;
			 
			btree_split_child(T, x, 0);

			int i = 0;
			if(k > x->bst.key[0]) i++;
			btree_insert_nonfull(T, x->bst.child[i], k);
		} else {
			btree_insert_nonfull(T, T->root, k); 
		}

		return 0;
	}


/**
	* @brief  归并结点
	* @param   
	* @retval 
	*/ 
	static int btree_merge(struct bTree *T, struct bTree_node *node, int idx)
    {
		//归并的只要思路，就是把node->bst.child[idx] 和 node->bst.child[idx+1]归并  ，然后插入node->key[idx]作为中间关键字

		int i=0;
		struct bTree_node *left = node->bst.child[idx];
		struct bTree_node *right = node->bst.child[idx+1];

		//data merge
		left->bst.key[T->degree-1] = node->bst.key[idx];			//node->key[idx]作为中间关键字
		for(i=0; i<T->degree-1; i++)
		{
			left->bst.key[T->degree+i] = right->bst.key[i];
		}
		if(!left->bst.leaf)
		{
			for(i=0; i<T->degree; i++)
			{
				left->bst.child[T->degree+i] = right->bst.child[i];
			}
		}
	
		left->bst.num += T->degree;    //还有一个key

		bTree_destroy_node(right);

		//node 删除node[idx],从后往前移 
		for(i=idx+1; i<node->bst.num; i++)
		{
			//这个拷贝的时候需要很注意
			node->bst.key[i-1] = node->bst.key[i];
			node->bst.child[i] = node->bst.child[i+1];
		}

		node->bst.child[node->bst.num] = NULL;
		node->bst.num -= 1;

		if(node->bst.num == 0) {
			T->root = left;
			bTree_destroy_node(node);
		}
	
		return 0;
	}


/**
	* @brief  B树删除结点,递归调用
	* @param   输出参数
	* @retval 
	*/ 
	static void btree_delete_key(struct bTree *T, struct bTree_node *node, Elemtype k) 
	{
		int idx = 0, i;

		if(node == NULL) return ;
		
		//遍历查找k是否在当前结点node中,这个是从0下标找起
		while(idx<node->bst.num && k > node->bst.key[idx]) {
			idx++;
		}
		printf("btree_delete_key %d %d %c %c\n", node->bst.num, node->bst.leaf, k, node->bst.key[idx]);
		if(idx < node->bst.num && k == node->bst.key[idx]) {
			//如果在当前结点上
			
			if(node->bst.leaf) {
				//判断是否是叶子结点,如果是叶子节点就直接删除
				//符合第1种情况
				printf("叶子点\n");
				//删除结点，把后面的结点往前移，这个是叶子结点，不用移动指针
				for(i=idx; i<node->bst.num-1; i++) {
					node->bst.key[i] = node->bst.key[i+1];
				}

				node->bst.key[node->bst.num-1] = 0;
				node->bst.num -= 1;
				
				if(node->bst.num == 0) {	//如果num=0，说明只剩根结点了
					bTree_destroy_node(node);				//释放根结点
					T->root = NULL;
				}
				
				return ;
			} 
			//后面的都不是叶子结点的
			else if(node->bst.child[idx]->bst.num >= T->degree)   {     //前于k的子结点y，至少包含T->degree各个关键字 
				//找出k在以**y为根的子树中的前驱k',递归的删除k'**，并在x中用k'代替k。
				printf("前驱\n");
				struct bTree_node *left = node->bst.child[idx];

				//用k'替换k
				node->bst.key[idx] = left->bst.key[node->bst.num-1];

				//递归替换
				btree_delete_key(T, left, left->bst.key[node->bst.num-1]); 
			}	
			else if(node->bst.child[idx+1]->bst.num >= T->degree)   {     //后于k的子结点z，至少包含T->degree各个关键字 
				//找出k在以**z为根的子树中的后驱k',递归的删除k'**，并在x中用k'代替k。
				printf("后驱\n");
				struct bTree_node *right = node->bst.child[idx+1];

				//用k'替换k
				node->bst.key[idx] = right->bst.key[0];

				//递归替换
				btree_delete_key(T, right, right->bst.key[0]); 
			}	
			else  { 	//y和z都包含T->degree-1个关键字，需要合并，然后在从y中递归删除k
				printf("其他\n");
				btree_merge(T, node, idx);						//合并
				btree_delete_key(T, node->bst.child[idx], k);	//递归删除
			}
		} else {
			//如果不在当前结点，就往孩子结点找
			struct bTree_node *child = node->bst.child[idx];
			
			if(child == NULL)  return ;

			if(child->bst.num == T->degree - 1) {    //判断孩子结点的个数是不是小于最小值，如果是就要特殊处理
				struct bTree_node *left = NULL;
				struct bTree_node *right = NULL;
				
				if (idx - 1 >= 0)
					left = node->bst.child[idx-1];
				if (idx + 1 <= node->bst.num) 
					right = node->bst.child[idx+1];

				if((left && left->bst.num >= T->degree) ||
					(right && right->bst.num >= T->degree))  {
						
						int richR = 0;
						if(right) richR = 1;
						if (left && right) richR = (right->bst.num > left->bst.num) ? 1 : 0;
						printf("右孩子\n");
						if(right && right->bst.num >= T->degree && richR) {   //找到右边兄弟替补
							//先把node结点的数据往child里放,放到child最后一个key中
							child->bst.key[child->bst.num] = node->bst.key[idx];
							//把right的第一个孩子指针挂接到child的最后一个指针上
							child->bst.child[child->bst.num+1] = right->bst.child[0];
							child->bst.num++;

							//把右孩子结点往父节点提
							node->bst.key[idx] = right->bst.key[0];

							//右孩子结点往前移
							for(i=0; i<right->bst.num-1; i++) {
								right->bst.key[i] = right->bst.key[i+1];
								right->bst.child[i] = right->bst.child[i+1];
							}

							right->bst.child[right->bst.num-1] = right->bst.child[right->bst.num];
							right->bst.child[right->bst.num] = NULL;
							right->bst.num--;
						} else{   //找到左边兄弟替补
							//左边跟右边不是对称关系，操作有点不一样，不过大体都一样的
							printf("左孩子\n");
							//先移动child的结点，空出第一个结点，等到父节点node插入元素
							for(i=child->bst.num; i>0; i--) {
								child->bst.key[i] = child->bst.key[i-1];
								child->bst.child[i+1] = child->bst.child[i];
							}

							child->bst.child[1] = child->bst.child[0];	
							//把左边孩子最后一个孩子指针挂接到child的0
							child->bst.child[0] = left->bst.child[left->bst.num];
							//把父结点的关键字赋值给left的0下标
							child->bst.key[0] = node->bst.key[idx-1];
							child->bst.num++;

							//把左孩子的最后一个元素赋值给父节点的元素
							node->bst.key[idx-1] = left->bst.key[left->bst.num];
							left->bst.child[left->bst.num] = NULL;
							left->bst.num--;
						}
				} else if((!left || left->bst.num == T->degree-1) && //左右兄弟都小于T->degree-1的时候
					(!right || right->bst.num == T->degree-1)) {

					if(left && left->bst.num == T->degree-1) {   //左边兄弟存在，并且满足T->degree-1
						btree_merge(T, node, idx-1);	
						child = left;
					} else if(right && right->bst.num == T->degree-1) {  //右边兄弟存在，并且满足T->degree-1
						btree_merge(T, node, idx);
						btree_printf(T->root);
						printf("\n");
					}
				}
			}

			//如果不是，直接调用删除函数
			btree_delete_key(T, child, k);
		}		
	}


/**
	* @brief  B树删除结点
	* @param   输出参数
	* @retval 
	*/ 
	int bTree_delete(struct bTree *T, Elemtype k)
	{
		if(T == NULL)
			return -1;

		btree_delete_key(T, T->root, k);

		return 0;
	}

	/**
    * @brief  B树的创建
    * @param   输出参数
    * @retval 
    */ 
    int bTree_creat(struct bTree *T, int degree)
	{
		if(T == NULL)
			return -1;
		
		T->degree = degree;			//这里赋值了

		T->root = bTree_creat_node(T, 0, 1);

		return 0;
	}


	#if 1
	/**
		* @brief  B树遍历，递归遍历
		* @param	
		* @retval 
		*/ 
		static void btree_printf(struct bTree_node *node)
		{	
			int i = 0;
			if(node == NULL)
				return ;

			//遍历当前结点
			printf("keynum = %d is_leaf = %d\n", node->bst.num, node->bst.leaf);

			for(i=0; i<node->bst.num; i++) {
				printf("%c ", node->bst.key[i]);
			}

			printf("\n");
			for(i=0; i<=node->bst.num; i++) {
				btree_printf(node->bst.child[i]);
			}
			
		}


		int main()
		{
			int ret = -1;
			int i = 0;
			char key[26] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";


			struct bTree T = {0};		//B树头结点

			bTree_creat(&T, 3);
			
			//循环插入
			for(i=0; i<26; i++)
			{
				//printf("---------------  插入 %c\n", key[i]);
				bTree_insert(&T, key[i]);
				//btree_printf(T.root);
				//printf("\n");
			}

			btree_printf(T.root);
			printf("\n");
			//int k = 'Z';
			bTree_delete(&T, 'Z');
			bTree_delete(&T, 'U');
			bTree_delete(&T, 'O');
			printf("------------------- A\n");
			bTree_delete(&T, 'A');
			btree_printf(T.root);
			printf("\n");
			
			
			return 0;
	
		}
	#endif




    /**
    * @}
    */


/**
    * @}
    */

/**
    * @}
    */

/**
    * @}
    */

/************************ (C) 2020 HOME 深圳龙华 *****END OF FILE****/

